package algorithm;

import java.util.ArrayList;


public class BellmanFord {
	class Edge{
		int tail;
		int weight;
	}
	
	ArrayList<ArrayList<Edge>> vertices;
	int [][]A;
	int verticesCount;
	int edgesCount;
	final static int MAX = 0x7FFFFFFF;
	public void InitData(){
		DataReader reader = new DataReader();
		reader.SetFilename("C:\\tmp\\g3.txt");
		
		String str;
		str = reader.GetNextLine();
		String[] parser = str.split(" ");
		verticesCount = Integer.parseInt(parser[0]);
		edgesCount = Integer.parseInt(parser[1]);
		A = new int[2][verticesCount + 1];
		
		vertices = new ArrayList<ArrayList<Edge>>(verticesCount + 1);
		for(int i = 0; i < verticesCount + 1; i++)
		{
			ArrayList<Edge> edgeList = new ArrayList<Edge>();
			vertices.add(edgeList);
		}
		
		while((str = reader.GetNextLine()) != null)
		{
			parser = str.split(" ");
			Edge edge = new Edge();
			edge.tail = Integer.parseInt(parser[0]);
			edge.weight = Integer.parseInt(parser[2]);
			int index = Integer.parseInt(parser[1]);
			ArrayList<Edge> edgeList = vertices.get(index);
			edgeList.add(edge);
		}
		
		//add vertex 0 to every vertex with weight 0
		for(int i = 0; i < verticesCount + 1; i++)
		{
			Edge edge = new Edge();
			edge.tail = 0;
			edge.weight = 0;
			ArrayList<Edge> edgeList = vertices.get(i);
			edgeList.add(edge);
		}
		
		//initialize A
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < verticesCount + 1; j++)
			{
				A[i][j] = MAX;
			}
		}
		A[0][0] = 0;
	}
	
	public void PrintData(){
		for(int i = 1; i < verticesCount + 1; i++)
		{
			ArrayList<Edge> edgeList = vertices.get(i);
			for(int j = 0; j < edgeList.size(); j++){
				Edge e = edgeList.get(j);
				System.out.print(e.tail + "\t" + i + "\t" + e.weight + "\n");
			}
		}
	}

	public int GetMinCurValue(int last[], int index, ArrayList<Edge> eList){
		int min = last[index];
		
		for(int i = 0; i < eList.size(); i++)
		{
			Edge e = eList.get(i);
			if(last[e.tail] < MAX){
				if(min > last[e.tail] + e.weight)
				{
					min = last[e.tail] + e.weight;
				}
			}
		}
		return min;
	}
	public void RunBellmanFord(){
		int last[] = A[0];
		int cur[] = A[1];
		for(int i = 1; i < verticesCount + 2; i++){
			for(int j = 0; j < verticesCount + 1; j++){
				//A[i][j] = min(A[i-1, j], min(A[i-1, w] + Cwj})
				ArrayList<Edge> eList = vertices.get(j);
				cur[j] = GetMinCurValue(last, j, eList);
			}
			int temp[] = last;
			last = cur;
			cur = temp;
		}
		
		boolean bNegativeCycle = false;
		for(int i = 0; i < verticesCount + 1; i++){
			if(last[i] != cur[i] && cur[i] != MAX)
			{
				bNegativeCycle = true;
				break;
			}
		}
		
		if(bNegativeCycle)
			System.out.println("there is a netative cycle");
		else
			System.out.println("there is no negative cycle");
	}
}
